import random
from typing import *


class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        st = set()
        for l, s in positions:
            st.add(l)
            st.add(l + s - 1)  # 右边开区间保证搭边能落
        d = dict()
        r = 1
        for num in sorted(st):
            d[num] = r
            r += 1
        n = len(st) * 4 + 1
        height = [0] * n
        mx = [0] * n

        def push(id):
            if height[id] > 0:
                height[id * 2] = height[id * 2 + 1] = height[id]
                mx[id * 2] = mx[id * 2 + 1] = height[id]
                height[id] = 0

        def update(id, L, R, l, r, h):
            if l <= L and R <= r:
                height[id] = h
                mx[id] = h
                return
            push(id)
            mid = (L + R) // 2
            if l <= mid:
                update(id * 2, L, mid, l, r, h)
            if r > mid:
                update(id * 2 + 1, mid + 1, R, l, r, h)
            mx[id] = max(mx[id * 2], mx[id * 2 + 1])

        def query(id, L, R, l, r):
            if l <= L and R <= r:
                return mx[id]
            push(id)
            mid = (L + R) // 2
            ans = 0
            if l <= mid:
                ans = query(id * 2, L, mid, l, r)
            if r > mid:
                ans = max(ans, query(id * 2 + 1, mid + 1, R, l, r))
            return ans

        ans = []
        for l, s in positions:
            li, si = d[l], d[l + s - 1]
            q = query(1, 1, r, li, si)
            update(1, 1, r, li, si, q + s)
            ans.append(mx[1])
        return ans


s = Solution()
print(s.fallingSquares([[1, 2], [2, 3], [6, 1]]))  #
print(s.fallingSquares([[100, 100], [200, 100]]))  #
print(
    [5, 7, 10, 18, 18, 18, 18, 18, 28, 37]
    == s.fallingSquares(
        [
            [70, 5],
            [15, 7],
            [31, 10],
            [38, 8],
            [70, 10],
            [52, 8],
            [20, 7],
            [32, 5],
            [38, 10],
            [43, 9],
        ]
    )
)
# cs = []
# for i in range(10):
#     cs.append([random.randint(1, 100), random.randint(5, 10)])
# print(cs)
from typing import *


class SegmentTree:

    def __init__(self, ceil: int = None, nums: List[int] = None) -> None:
        self.n = ceil if ceil is not None else len(nums)
        self.sums = [0] * (self.n << 2)
        self.nums = nums
        self.update = [None] * (self.n << 2)
        if nums is not None:
            self.build(0, self.n - 1, 1)

    def build(self, s: int, e: int, node: int):
        if s == e:
            self.sums[node] = self.nums[s]
            return
        m = s + ((e - s) >> 1)
        self.build(s, m, node << 1)
        self.build(m + 1, e, node << 1 | 1)
        self.sums[node] = self.sums[node << 1] + self.sums[node << 1 | 1]

    def __pushdown(self, s: int, e: int, node: int):
        if self.update[node] != None:
            val = self.update[node]
            m = ((e - s) >> 1) + s
            self.sums[node << 1] = (m - s + 1) * val
            self.update[node << 1] = val
            self.sums[node << 1 | 1] = (e - m) * val
            self.update[node << 1 | 1] = val
            self.update[node] = None

    def do_update_range(self, L: int, R: int, val: int) -> None:
        self.__update(0, self.n - 1, 1, L, R, val)

    def do_update_index(self, index: int, val: int) -> None:
        self.__update(0, self.n - 1, 1, index, index, val)

    # 更新逻辑
    def __update(self, s: int, e: int, node: int, L: int, R: int, val: int):
        if L <= s and e <= R:
            self.update[node] = val
            self.sums[node] = val * (e - s + 1)
            if L == R:
                self.nums[L] = val
            return
        m = ((e - s) >> 1) + s
        self.__pushdown(s, e, node)
        if L <= m:
            self.__update(s, m, node << 1, L, R, val)
        if m < R:
            self.__update(m + 1, e, node << 1 | 1, L, R, val)
        self.sums[node] = self.sums[node << 1] + self.sums[node << 1 | 1]

    def do_query_sum(self, L: int, R: int) -> int:
        return self.__query_sum(0, self.n - 1, 1, L, R)

    def __query_sum(self, s: int, e: int, node: int, L: int, R: int):
        if L <= s and e <= R:
            return self.sums[node]
        self.__pushdown(s, e, node)
        m = ((e - s) >> 1) + s
        ans = 0
        if L <= m:  # 左边有任务
            ans += self.__query_sum(s, m, node << 1, L, R)
        if m < R:  # 右边有任务
            ans += self.__query_sum(m + 1, e, node << 1 | 1, L, R)
        return ans

